package com.base.dynamicprograming;

/**
 * 516. 最长回文子序列
 * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 *
 * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年12月13日 16:10
 */
public class LongestPalindromeSubseq {
    //    dp[i][j]表示s[i..j]代表的字符串的最长回文子序列
    //    三种状态
    //    d[i][i]=1
    //    dp[i][j] = dp[i+1][j-1]+2 当s[i]=s[j]
    //    dp[i][j]=max(dp[i+1][j],dp[i][j-1]) 当s[i]!=s[j] 取s[i+1..j] 和s[i..j-1]中最长的 由于dp[i][j]需要dp[i+1][j]所以需要逆序枚举s的长度，而又因为j是递增的，所以在求解dp[i][j]时,dp[i][j-1]肯定已经求解过
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        char[] charArray = s.toCharArray();
        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // 长度从2 到 n
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n; i++) {
                // 左端点 i
                // 右端点 j - i + 1 = len
                // j = len + i -1;
                int j = len+ i- 1;
                if(j>n-1){
                    break;
                }
                if(charArray[i] == charArray[j]){
                    if(len<3){
                        dp[i][j] = 2;
                    }else {
                        dp[i][j] = dp[i+1][j-1] + 2;
                    }
                }else {
                    if(len<3){
                        dp[i][j] = 1;
                    }else {
                        // 这里需要注意的
                        dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                    }
                }

                if(dp[i][j]>maxLen){
                    maxLen = dp[i][j];
                }
            }
        }
        return maxLen;

    }
}
